When storing information that is secret (hereinafter written as secret information), there is a threat of loss or destruction of the secret information and a threat of theft of the secret information. Generation of a copy of the secret information is effective against the threat of loss or destruction of the secret information. However, when the copy is generated, the threat of the theft would increase.
As one of means for solving such a problem, secret sharing schemes are provided. A(k,n) threshold scheme, which is one of the secret sharing schemes, has the following feature. In this method, secret information is encoded into n distributed information, and the secret information can be completely reconstructed by collection of arbitrary k or more pieces of the n distributed information. However, when (k−1) pieces of the distributed information are just collected, information on the secret information cannot entirely be obtained. Accordingly, even if the (k−1) pieces of the distributed information are stolen, the secret information will not leak. Further, even if (n−k) pieces of the distributed information are destroyed, the secret information can be reconstructed.
Non-patent Document 1 describes use of a (k−1)-degree polynomial, as the (k,n) threshold scheme. In the method described in Non-patent Document 1, a finite field GF(p) for a prime number p or a power of the prime number p is used as a data set of secret information. Then, points (x1, f(x1)), . . . , (xn, f(xn)) on a random (k−1)-degree polynomial f(x) on the finite field GF(p) having the secret information in its constant term are set to distributed information. The (k−1)-degree polynomial can be uniquely reconstructed from k pieces of the distributed information, and the secret information s, which is a value f(0) can be reconstructed. The value f(0) cannot be determined from (k−1) or less pieces of the distributed information. Thus, information on the secret information s never leaks.
In a method described in Non-patent Document 2, points (x1, f(x1)), . . . (xn, f(xn)) on a random (k−1)-degree polynomial f(x) on a finite field GF(p) are set to distributed information, as in the method described in Non-patent Document 1. By embedding secret information in first and higher-degree coefficients other than the constant term of the (k−1)-degree polynomial, for example, the size of the distributed information can be reduced. However, there is a disadvantage that information on the secret information leaks from (k−1) or less pieces of the distributed information. The size of the distributed information is the number of elements in the group of the distributed information.
As a common property between the methods described in Non-patent Documents 1 and 2, it can be pointed out that numbers assigned to apparatuses that store the distributed information can be used as xi (i=1, . . . , n). In the following description, f(xi) for xi is referred to as the distributed information on xi.
In a method described in Non-patent Document 3, cheating is detected in the (k,n) threshold scheme described in Non-patent Documents 1 and 2. Assume that a probability capable of detecting cheating is set to (1−ε) and secret information is selected from a group of elements in which the number of the elements is s. Then, distributed information are elements of a group in which the number of the elements is ((s−1)(k−1)/ε+k)2. In this method, even if a maximum of (k−1) pieces of k distributed information used at a time of reconstruction is tampered, cheating can be detected.
Non-patent Document 4 describes a method in which the size of distributed information is smaller than that in the method described in Non-patent Document 3 and cheating can be detected even if a maximum of (k−1) pieces of distributed information is tampered.
Non-Patent Document 1:
Adi Shamir, “How to share a secret”, Comm. ACM, 1979, 22(11), 612-613
Non-Patent Document 2:
G R Blakley, Catherine Meadows, Security of Ramp schemes, Proceedings of CRYPTO 84, LNCS, 1985, 196, Pages: 242-268
Non-Patent Document 3:
Martin Tompa, Heather Woll, How to Share a Secret with Cheaters, Advances in Cryptology—CRYPTO' 86, 263 LNCS, 1987, pp. 261-265
Non-Patent Document 4:
Wakaha Ogata, Kaoru Kurosawa, Douglas R Stinson, “Optimum Secret Sharing Scheme Secure Against Cheating”, SIAM J. Discrete Math, 2006, vol. 20, no 1, p. 79-95